#include <stdio.h>
#include <stdlib.h>
// #include "libtas.h"
#include "typ.h"

int getPere(int n){

	return (n-1)/2;

}

int getDroit(int n){

	return 2*n+1;

}

int getGauche(int n){

	return 2*n+2;

}

void echanger(Tas* t, int i1, int i2){

	TypArete* temp = t->tab[i1];
	t->tab[i1] = t->tab[i2];
	t->tab[i2] = temp;

}

void entasser(Tas* t, int n){

	TypArete* areteN = t->tab[n];

	int g = getGauche(n);
	int d = getDroit(n);

	TypArete* areteG;
	TypArete* areteD;

	double valn = areteN->poids;

	double valg;
	double vald;
	
	int min = n;
	double val_min = valn;

	if (g < t->tailleTas){
		areteG = t->tab[g];
		valg = areteG->poids;

		if(valg < val_min){
			min = g;
			val_min = valg;
		}
    }
    

    if (d < t->tailleTas){
      areteD = t->tab[d];
      vald = areteD->poids;

      if(vald < val_min){
        min = d;
      }
    }

    if (min != n){
        echanger(t,n,min);
        entasser(t,min);
    }
}

void retirerRacine(Tas* t, TypArete* arete){

	arete->v1 = t->tab[0]->v1;
	arete->v2 = t->tab[0]->v2;
	arete->poids = t->tab[0]->poids;

	t->tailleTas--;

	t->tab[0]->v1 = t->tab[t->tailleTas]->v1;
	t->tab[0]->v2 = t->tab[t->tailleTas]->v2;
	t->tab[0]->poids = t->tab[t->tailleTas]->poids;

	// free(t->tab[t->tailleTas]);
	
	t->tab = realloc(t->tab,t->tailleTas * sizeof(TypArete*));

	entasser(t,0);

	return;

}


void faireTas(Tas* t){
  int i;
  for(i=t->tailleTas/2;i>=0;i--){
    entasser(t,i);
  }
}

void afficherTas(Tas* t){
  int i ;

  // int hauteur = firstset(t->tailleTas);

  for(i=0;i<t->tailleTas;i++){
    
    printf("(%d,%d)\t %f\n",t->tab[i]->v1,t->tab[i]->v2,t->tab[i]->poids);
    
  }
}

void echangerV2(TasV2* t, int i1, int i2){

  double temp = t->tabValeur[i1];
  t->tabValeur[i1] = t->tabValeur[i2];
  t->tabValeur[i2] = temp;

  int i_temp = t->tabSommet[i1];
  t->tabSommet[i1] = t->tabSommet[i2];
  t->tabSommet[i2] = i_temp;

}

void entasserV2(TasV2* t, int n){

    
    int g = getGauche(n);
    int d = getDroit(n);

    double valn = t->tabValeur[n];
    
    int min = n;

    if (g < t->tailleTas && t->tabValeur[g] < valn){
        min = g;
    }
    
    if (d < t->tailleTas && t->tabValeur[d] < t->tabValeur[min]){
        min = d;
    }

    if (min != n){
        echangerV2(t,n,min);
        entasserV2(t,min);
    }
}

void faireTasV2(TasV2* t){
  int i;
  for(i=t->tailleTas/2;i>=0;i--){
    entasserV2(t,i);
  }
}

void afficherTasV2(TasV2* t){
  int i ;

  // int hauteur = firstset(t->tailleTas);

  for(i=0;i<t->tailleTas;i++){
    
    printf("(%d , %f)\n",t->tabSommet[i],t->tabValeur[i]);
    
  }
}